//给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。 
//
// 岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。 
//
// 
// 
// 你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。 
//
// 返回必须翻转的 0 的最小数目。 
// 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：grid = [[0,1],[1,0]]
//输出：1
// 
//
// 示例 2： 
//
// 
//输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
//输出：2
// 
//
// 示例 3： 
//
// 
//输入：grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// n == grid.length == grid[i].length 
// 2 <= n <= 100 
// grid[i][j] 为 0 或 1 
// grid 中恰有两个岛 
// 
// Related Topics深度优先搜索 | 广度优先搜索 | 数组 | 矩阵 
//
// 👍 274, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

class ShortestBridge {
    public static void main(String[] args) {
        Solution solution = new ShortestBridge().new Solution();
        solution.shortestBridge(new int[][]{{1, 1, 1, 1, 1}, {1, 0, 0, 0, 1}, {1, 0, 1, 0, 1}, {1, 0, 0, 0, 1}, {1, 1, 1, 1, 1}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int m, n;

        public int shortestBridge(int[][] grid) {
            this.m = grid.length;
            this.n = grid[0].length;
            Queue<int[]> queue = new LinkedList<>();
            boolean[][] flag = new boolean[m][n];
            // DFS将一个岛屿入队,再通过BFS搜素另一个岛屿
            for (int i = 0; i < m; i++) {
                boolean a = false;
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1) {
                        dfs(grid, i, j, flag, queue);
                        a = true;
                        break;
                    }
                }
                if (a) break;
            }

            // BFS搜索另一个岛屿
            int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            int level = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int k = 0; k < size; k++) {
                    int[] poll = queue.poll();
                    int i = poll[0], j = poll[1];
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x < 0 || y < 0 || x >= m || y >= n || flag[x][y]) continue;
                        flag[x][y] = true;
                        queue.offer(new int[]{x, y});
                        if (grid[x][y] == 1) return level;
                    }
                }
                level++;
            }

            return level;
        }

        public void dfs(int[][] grid, int i, int j, boolean[][] flag, Queue<int[]> queue) {
            if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0 || flag[i][j]) return;
            flag[i][j] = true;
            grid[i][j] = 0;
            queue.offer(new int[]{i, j});
            dfs(grid, i - 1, j, flag, queue);
            dfs(grid, i + 1, j, flag, queue);
            dfs(grid, i, j - 1, flag, queue);
            dfs(grid, i, j + 1, flag, queue);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
